package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @Classname LetterCombinations_0017
 * @Author happytaohaha
 * @Date 2020/4/1
 * @Description 17. 电话号码的字母组合
 *  O(3^N *4^M)  结果为： 3个数出现的出现和4个数每次出现
 *   回溯法： 学会对 map和数组的使用  的使用
 */
public class LetterCombinations_0017 {

    HashMap<String, String> hashMap = new HashMap<String, String>() {{
        put("2", "abc");
        put("3", "def");
        put("4", "ghi");
        put("5", "jkl");
        put("6", "mno");
        put("7", "pqrs");
        put("8", "tuv");
        put("9", "wxyz");
    }};

    List<String> result = new ArrayList<>();

    public List<String> letterCombinations(String digits) {
        if (digits.length() != 0) {
            backtrack("", digits);
        }
        return result;
    }

    private void backtrack(String combination, String next_digits) {
        if(next_digits.length()==0){
            result.add(combination);
        }else{
            String index = next_digits.substring(0,1);
            String letters = hashMap.get(index);
            for(int i = 0; i < letters.length(); i++){
                backtrack(combination+letters.charAt(i),next_digits.substring(1));
            }
        }

    }


    public static void main(String[] args) {
        LetterCombinations_0017 letterCombinations_0017= new LetterCombinations_0017();
        System.out.println(letterCombinations_0017.letterCombinations("23"));
        System.out.println();
    }
}
